package top.ezzz.base;

import top.ezzz.user.IntMap;
import top.ezzz.user.NoteMap;

import java.util.ArrayList;


public class CoinChange {

    public static void main(String[] args) {
        int coins[] = {1, 2, 5};
        int target = 11;
        int solution = coinSolution2(coins, target);
        System.out.println("solution = " + solution);

    }

    public static int coinSolution2(int coins[], int target) {
        int res = Integer.MAX_VALUE;
        ArrayList<Integer> list = new ArrayList<>();
        for (int i = 0; i < target; i++) {
            list.add(target);
        }
        list.add(0, 0);

        for (int i = 0; i < list.size(); i++) {
            for (int coin : coins) {
                if (i - coin < 0) continue;
                int min = Math.min(list.get(i), 1 + list.get(i - coin));
                list.set(i, min);
            }
        }
        if (list.get(target) == target + 1) {
            return -1;
        }
        return list.get(target);
    }

    public static int coinSolution1(int coins[], int target) {
        int res = Integer.MAX_VALUE;
        if (target == 0) {
            return 0;
        }
        if (target < 0) {
            return -1;
        }
        IntMap shareMap = NoteMap.shareMap;
        for (int cn : coins) {
            if (shareMap.get(target) != null) {
                return shareMap.get(target);
            }
            int solution = coinSolution(coins, target - cn);
            if (solution == -1) continue;
            res = Math.min(res, 1 + solution);
            if (res >= (1 + solution)) {
                NoteMap.shareList.add(cn);
            }
            //System.out.println("cn = " + cn);
        }
        shareMap.set(target, res);
        return res;
    }

    public static int coinSolution(int coins[], int target) {
        int res = Integer.MAX_VALUE;
        if (target == 0) {
            return 0;
        }
        if (target < 0) {
            return -1;
        }
        for (int cn : coins) {
            int solution = coinSolution(coins, target - cn);
            if (solution == -1) continue;
            res = Math.min(res, 1 + solution);
            //System.out.println("cn = " + cn);
        }
        return res;
    }


}
